package q735_asteroidCollision;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    /*
    使用栈可以简单解决该问题
    首先使用栈依次压入当前行星 注意行星的运动具有方向 所以只有当前asteroid < 0 && stack.peek() > 0
    才会相撞 否则不会
    那么每次遇到该情况进行弹出并判断即可 然后更新asteroid
    最后依次将栈中元素放回一个数组
     */
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new LinkedList<>();
        for (int asteroid : asteroids) {
            while (stack.size() >= 1 && asteroid < 0 && stack.peek() > 0) {
                int peek = stack.pop();
                if (Math.abs(peek) > Math.abs(asteroid)) {
                    asteroid = peek;
                } else if (peek + asteroid == 0) {
                    asteroid = 0;
                }
            }
            if (asteroid != 0) stack.push(asteroid);
        }
        int[] ans = new int[stack.size()];
        for (int i = ans.length - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}
